"""
Problem 70: https://projecteuler.net/problem=70

Euler's Totient function, φ(n) [sometimes called the phi function], is used to
determine the number of positive numbers less than or equal to n which are
relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than
nine and relatively prime to nine, φ(9)=6.

The number 1 is considered to be relatively prime to every positive number, so
φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation
of 79180.

Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and
the ratio n/φ(n) produces a minimum.

"""


# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/24
'''





from commonfuncs.primefunctools import isPrime
def solution(limit: int = 10000000) -> list:
    '''
    φ(n) = n(1-1/p1)(1-1/p2)(1-1/p3)....(1-1/pk), pi is prime factor of n
    n/φ(n) = 1 /
              / (1-1/p1)(1-1/p2)(1-1/p3)....(1-1/pk)  
    so, min{ n/φ(n) | n ~ φ(n)}  
        <==> max{ (1-1/p1)(1-1/p2)(1-1/p3)....(1-1/pk) | n ~ φ(n) }

    when n is largest prime, n/φ(n) = n/(n-1) is a minimum, 
    but n !~ φ(n)=n-1

    consider n = p*q < 10^d, p,q are primes as large as possible,
             and n ~ (p-1)(q-1)

             assume p <= q, then p <= 10^(d/2)

    if n = p1*p2*p3, (1-1/p1)(1-1/p2)(1-1/p3) < (1-1/p1)(1-1/p2)
    so (p1*p2*p3)/φ(p1*p2*p3) > (p1*p2)/φ(p1*p2), we chose p1*p2


    '''

    def isPermutation(p,q):
        return sorted(list(str(p*q))) == sorted(list(str((p-1)*(q-1))))

    def maxq(p):  # q >= p
        tmp = limit//p
        if not tmp%2:
            tmp -= 1
        for q in range(tmp,p-2,-2):
            if isPrime(q) and isPermutation(p, q):
                return p,q
        return False



    primes = [i for i in range(int(limit**0.5)+1) if isPrime(i)]
    pair = []

    for p in primes[::-1]:
        pq = maxq(p)

        if not pq:
            continue
        if pair and pq[1] <= pair[-1][1]:
            continue

        print(pq)
        pair.append(pq)

    # print(pair)

    res = 0
    respq=2
    for pq in pair:
        tmp = (1-1/pq[0])*(1-1/pq[1])
        if tmp > res:
            res = tmp
            respq = pq
    
    return respq, 1/res

    


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # ((2339, 3557), 1.0007090511248113)
